package com.itcast.demo.test;

import java.util.ArrayList;

/**
 * @author zheng.zhang
 */
public class Spiral {

    public static void main(String[] args) {
        Spiral spiral = new Spiral();
        //int[][] input = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
        int[][] input = {{1}};
        ArrayList<Integer> result = spiral.spiralOrder(input);
        System.out.println(result);
    }

    /**
     * 给定一个m x n大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。
     * 输入：[[1,2,3],[4,5,6],[7,8,9]]
     * 返回值：[1,2,3,6,9,8,7,4,5]
     *
     * @param matrix 二维数组
     * @return 螺旋数组
     */
    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> arr = new ArrayList<>();
        if (matrix.length == 0) {
            return arr;
        }
        int rowBegin = 0;
        int rowEnd = matrix.length - 1;
        int colBegin = 0;
        int colEnd = matrix[0].length - 1;
        while (rowBegin <= rowEnd && colBegin <= colEnd) {
            // 方向: -→
            for (int i = colBegin; i <= colEnd; i++) {
                arr.add(matrix[rowBegin][i]);
            }
            rowBegin++;
            // 方向: ↓
            for (int i = rowBegin; i <= rowEnd; i++) {
                arr.add(matrix[i][colEnd]);
            }
            colEnd--;
            // 方向: ←-
            if (rowBegin <= rowEnd) {
                for (int i = colEnd; i >= colBegin; i--) {
                    arr.add(matrix[rowEnd][i]);
                }
            }
            rowEnd--;
            // 方向: ↑
            if (colBegin <= colEnd) {
                for (int i = rowEnd; i >= rowBegin; i--) {
                    arr.add(matrix[i][colBegin]);
                }
            }
            colBegin++;
        }
        return arr;
    }
}
